/LMAR=0/XLINE=10/FONT#0=NONM/FONT#1=BAXM30/FONT#2=MATH30/FONT#3=FIX25/FONT#4=GRKL30/FONT#5=ZERO30
␈↓ α∧␈↓␈↓ ¬∞S T A N F O R D   U N I V E R S I T Y
␈↓"β␈↓ α∧␈↓␈↓ ∧⊗MOST RECENT COMPUTER SCIENCE REPORTS - 1979
␈↓"β␈↓ α∧␈↓No. 4␈↓ CJune

␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓-␈↓ v-

␈↓"β␈↓ α∧␈↓    Listed␈α∞here␈α∞are␈α∞abstracts␈α
of␈α∞the␈α∞most␈α∞recent␈α
reports␈α∞published␈α∞by␈α∞the␈α∞Department␈α
of
␈↓ α∧␈↓Computer Science at Stanford University.

␈↓"β␈↓ α∧␈↓    TO␈α
REQUEST␈α
REPORTS:␈α
 Check␈α
the␈α
appropriate␈αplaces␈α
on␈α
the␈α
enclosed␈α
order␈α
form,␈αand
␈↓ α∧␈↓return␈α∞the␈α∞entire␈α∂order␈α∞form␈α∞page␈α∂(including␈α∞mailing␈α∞label)␈α∞by␈α∂August␈α∞24,␈α∞1979.␈α∂ In␈α∞many
␈↓ α∧␈↓cases␈α
we␈α
can␈α∞print␈α
only␈α
a␈α∞limited␈α
number␈α
of␈α
copies,␈α∞and␈α
requests␈α
will␈α∞be␈α
filled␈α
on␈α∞a␈α
first
␈↓ α∧␈↓come,␈αfirst␈αserve␈αbasis.␈α If␈αthe␈αcode␈α(FREE)␈αis␈αprinted␈αon␈αyour␈αmailing␈αlabel,␈αyou␈αwill␈αnot␈αbe
␈↓ α∧␈↓charged␈α
for␈α
hardcopy.␈α
 This␈α
exemption␈α
from␈α
payment␈α
is␈α
limited␈α
primarily␈α
to␈α∞libraries.␈α
 (The
␈↓ α∧␈↓costs␈αshown␈αinclude␈αall␈αapplicable␈αsales␈αtaxes.␈α PLEASE␈αSEND␈αNO␈αMONEY␈αNOW,␈αWAIT␈αUNTIL
␈↓ α∧␈↓YOU GET AN INVOICE.)

␈↓"β␈↓ α∧␈↓    ALTERNATIVELY:␈α Copies␈αof␈α
most␈αStanford␈αCS␈α
Reports␈αmay␈αbe␈α
obtained␈αby␈αwriting␈α
(about
␈↓ α∧␈↓2␈α≠months␈α≠after␈α≠the␈α≠MOST␈α~RECENT␈α≠CS␈α≠REPORTS␈α≠listing)␈α≠to␈α≠NATIONAL␈α~TECHNICAL
␈↓ α∧␈↓INFORMATION␈α
SERVICE,␈α
5285␈α
Port␈α
Royal␈α
Road,␈α
Springfield,␈α
Virginia␈α
22161.␈α∞ Stanford␈α
Ph.D.
␈↓ α∧␈↓theses␈α∪are␈α∪available␈α∪from␈α∪UNIVERSITY␈α∪MICROFILMS,␈α∪300␈α∪North␈α∪Zeeb␈α∪Road,␈α∀Ann␈α∪Arbor,
␈↓ α∧␈↓Michigan 48106.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-729
␈↓"β␈↓ α∧␈↓    A UNIFIED APPROACH TO PATH PROBLEMS
␈↓"β␈↓ α∧␈↓Author:  Robert Endre Tarjan
␈↓"β␈↓ α∧␈↓43 pages␈↓ 
\Cost: $2.90

␈↓"β␈↓ α∧␈↓    We␈αdescribe␈αa␈αgeneral␈αmethod␈αfor␈αsolving␈αpath␈αproblems␈αon␈αdirected␈αgraphs.␈α Such␈α
path
␈↓ α∧␈↓problems␈α∞include␈α∞finding␈α∞shortest␈α∞paths,␈α∞solving␈α∞sparse␈α∞systems␈α∞of␈α∞llinear␈α∞equations,␈α
and
␈↓ α∧␈↓carrying␈αout␈αglobal␈αflow␈αanalysis␈αof␈αcomputer␈αprograms.␈α Our␈αmethod␈αconsists␈αof␈αtwo␈αsteps.
␈↓ α∧␈↓First,␈α∞we␈α
construct␈α∞a␈α∞collection␈α
of␈α∞regular␈α
expressions␈α∞representing␈α∞sets␈α
of␈α∞paths␈α∞in␈α
the
␈↓ α∧␈↓graph.␈α∂ This␈α⊂can␈α∂be␈α⊂done␈α∂by␈α⊂using␈α∂any␈α∂standard␈α⊂algorithm,␈α∂such␈α⊂as␈α∂Gaussian␈α⊂or␈α∂Gauss-
␈↓ α∧␈↓Jordan␈α⊂elimination.␈α∂ Next,␈α⊂we␈α∂apply␈α⊂a␈α∂natural␈α⊂mapping␈α∂from␈α⊂regular␈α∂expressions␈α⊂into␈α∂the
␈↓ α∧␈↓given␈α⊃problem␈α⊂domain.␈α⊃ We␈α⊂exhibit␈α⊃the␈α⊃mappings␈α⊂required␈α⊃to␈α⊂find␈α⊃shortest␈α⊃paths,␈α⊂solve
␈↓ α∧␈↓sparse␈αsystems␈αof␈αlinear␈α
equations,␈αand␈αcarry␈αout␈α
global␈αflow␈αanalysis.␈α Our␈αresults␈α
provide
␈↓ α∧␈↓a␈α∂general-purpose␈α∞algorithm␈α∂for␈α∞solving␈α∂any␈α∞path␈α∂problem,␈α∞and␈α∂show␈α∞that␈α∂the␈α∂problem␈α∞of
␈↓ α∧␈↓constructing path expressions is in some sense the most general path problem.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-730
␈↓"β␈↓ α∧␈↓    QUALIFYING EXAMINATIONS IN COMPUTER SCIENCE, 1965-1978
␈↓"β␈↓ α∧␈↓Editor:  Frank M. Liang
␈↓"β␈↓ α∧␈↓238 pages␈↓ 
\Cost: $8.40

␈↓"β␈↓ α∧␈↓    Since␈α→1965,␈α→the␈α→Stanford␈α~Computer␈α→Science␈α→Department␈α→has␈α~periodically␈α→given
␈↓ α∧␈↓"qualifying␈α∩examinations"␈α∩as␈α∩one␈α∩of␈α⊃the␈α∩requirements␈α∩of␈α∩its␈α∩graduate␈α∩program.␈α⊃ These
␈↓ α∧␈↓examinations␈α∃are␈α∃given␈α∃in␈α∃each␈α∃of␈α∃six␈α∃subareas␈α∃of␈α∃computer␈α∃science:␈α∃ Programming
␈↓ α∧␈↓Languages␈α
and␈α
Systems,␈α
Artificial␈α
Intelligence,␈α
Numerical␈α
Analysis,␈α
Computer␈α
Design,␈α
Theory
␈↓ α∧␈↓of␈αComputation,␈αand␈αAnalysis␈αof␈αAlgorithms.␈α This␈αreport␈αpresents␈αthe␈αquestions␈αfrom␈αthese
␈↓ α∧␈↓examinations, and also the associated reading lists.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-731
␈↓"β␈↓ α∧␈↓    STANFORD PASCAL VERIFIER USER MANUAL
␈↓"β␈↓ α∧␈↓Authors:  D.C. Luckham, S.M. German, F.W. von Henke, R.A. Karp, P.W. Milne, D.C. Oppen,
␈↓"β␈↓ α∧␈↓              W. Polak & W.L. Scherlis
␈↓"β␈↓ α∧␈↓? pages␈↓ ≥Cost: $

␈↓"β␈↓ α∧␈↓    The␈αStanford␈α
Pascal␈αverifier␈αis␈α
an␈αinteractive␈αprogram␈α
verification␈αsystem.␈α It␈α
automates
␈↓ α∧␈↓much␈αof␈αthe␈αwork␈αnecessary␈αto␈αanalyze␈αa␈αprogram␈αfor␈αconsistency␈αwith␈αits␈αdocumentation,
␈↓ α∧␈↓and␈α⊂to␈α∂give␈α⊂a␈α∂rigorous␈α⊂mathematical␈α∂proof␈α⊂of␈α∂such␈α⊂consistency␈α∂or␈α⊂to␈α∂pin-point␈α⊂areas␈α∂of
␈↓ α∧␈↓inconsistency.␈α∞ It␈α
has␈α∞been␈α∞shown␈α
to␈α∞have␈α∞applications␈α
an␈α∞an␈α∞aid␈α
to␈α∞programming,␈α∞and␈α
to
␈↓ α∧␈↓have␈α⊃potential␈α⊃for␈α⊃development␈α⊃as␈α⊃a␈α⊃new␈α⊃and␈α⊃useful␈α⊃tool␈α⊃in␈α⊃the␈α⊃production␈α⊃of␈α⊂reliable
␈↓ α∧␈↓software.

␈↓"β␈↓ α∧␈↓    This␈α∀verifier␈α∀is␈α∃a␈α∀prototype␈α∀system.␈α∀ It␈α∃has␈α∀inadequacies␈α∀and␈α∀shortcomings.␈α∃ It␈α∀is
␈↓ α∧␈↓undergoing␈αcontinuous␈αimprovement,␈αand␈αis␈αexpected␈αto␈αbe␈αused␈αeventually␈α
in␈αconjunction
␈↓ α∧␈↓with␈α⊂other␈α⊂kinds␈α⊂of␈α⊂program␈α⊂analyzers.␈α⊂ The␈α⊂purpose␈α⊂of␈α⊂this␈α⊂manual␈α⊂is␈α⊂to␈α⊃introduce␈α⊂the
␈↓ α∧␈↓verifier␈α∪to␈α∪a␈α∪wider␈α∪group␈α∪of␈α∪users␈α∪for␈α∪experimentation.␈α∪ We␈α∪hope␈α∪to␈α∪encourage␈α∪both
␈↓ α∧␈↓feedback to help improve this system, and the development of other program analyzers.

␈↓"β␈↓ α∧␈↓    The␈α∩verfier␈α∩is␈α⊃coded␈α∩in␈α∩Maclisp,␈α∩a␈α⊃version␈α∩of␈α∩Lisp␈α⊃developed␈α∩at␈α∩M.I.T.␈α∩ for␈α⊃PDP-10
␈↓ α∧␈↓computers.␈α⊃ Versions␈α⊃of␈α⊃the␈α⊃verifier␈α⊃run␈α⊃under␈α⊃the␈α⊃TOPS␈α⊃20␈α⊃operating␈α⊃system␈α⊃and␈α⊃the
␈↓ α∧␈↓Stanford WAITS operating system.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-732
␈↓"β␈↓ α∧␈↓    NOTES ON INTRODUCTORY COMBINATORICS
␈↓"β␈↓ α∧␈↓Author: Donald R. Woods
␈↓"β␈↓ α∧␈↓120 pages␈↓ 
\Cost: $5.10

␈↓"β␈↓ α∧␈↓    In␈αthe␈α
spring␈αof␈α
1978,␈αProfessors␈α
George␈αPolya␈αand␈α
Robert␈αTarjan␈α
teamed␈αup␈α
to␈αteach
␈↓ α∧␈↓CS␈α150␈α--␈αIntroduction␈αto␈αCombinatorics.␈α This␈αreport␈αconsists␈αprimarily␈αof␈αthe␈αclass␈αnotes
␈↓ α∧␈↓and other handouts produced by the author as teaching assistant for the course.

␈↓"β␈↓ α∧␈↓    Among␈α~the␈α~topics␈α~covered␈α~are␈α~elementary␈α~subjects␈α~such␈α~as␈α~combinations␈α→and
␈↓ α∧␈↓permutations,␈α∀mathematical␈α∪tools␈α∀such␈α∀as␈α∪generating␈α∀functions␈α∪and␈α∀Polya's␈α∀Theory␈α∪of
␈↓ α∧␈↓Counting,␈α∪and␈α∪analyses␈α∪of␈α∪specific␈α∀problems␈α∪such␈α∪as␈α∪Ramsey␈α∪Theory,␈α∀matchings,␈α∪and
␈↓ α∧␈↓Hamiltonian and Eulerian paths.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-733
␈↓"β␈↓ α∧␈↓    A LOWER BOUND TO FINDING CONVEX HULLS
␈↓"β␈↓ α∧␈↓Author: Andrew Chi-Chih Yao
␈↓"β␈↓ α∧␈↓22 pages␈↓ 
\Cost: $2.35

␈↓"β␈↓ α∧␈↓    Given␈α⊂a␈α⊂set␈α⊃S␈α⊂of␈α⊂␈↓↓n␈↓␈α⊃distince␈α⊂points␈α⊂␈↓↓{(x␈↓#vi␈↓#,y␈↓#vi␈↓#)␈α⊃|␈α⊂0␈α⊂␈↓β≤␈↓↓␈α⊂i␈α⊃<␈α⊂n}␈↓,␈α⊂the␈α⊃␈↓↓convex␈α⊂hull␈α⊂problem␈↓␈α⊃is␈α⊂to
␈↓ α∧␈↓determine␈α
the␈α∞vertices␈α
of␈α∞the␈α
convex␈α∞hull␈α
H(S).␈α
 All␈α∞the␈α
known␈α∞algorithms␈α
for␈α∞solving␈α
this
␈↓ α∧␈↓problem␈α∂have␈α∂a␈α∞worst-case␈α∂running␈α∂time␈α∂of␈α∞␈↓↓cn␈α∂log␈α∂n␈↓␈α∂or␈α∞higher,␈α∂and␈α∂employ␈α∂only␈α∞␈↓↓quadratic
␈↓ α∧␈↓↓tests␈↓,␈αi.e.,␈αtests␈αof␈αthe␈αform␈α␈↓↓f(x␈↓#v0␈↓#,y␈↓#v0␈↓#,x␈↓#v1␈↓#,y␈↓#v1␈↓#,...,x␈↓#vn-1␈↓#,y␈↓#vn-1␈↓#) : 0␈↓␈αwith␈α␈↓↓f␈↓␈αbeing␈αany␈αpolynomial␈αof
␈↓ α∧␈↓degree␈α∪not␈α∩exceeding␈α∪2.␈α∩ In␈α∪this␈α∩paper,␈α∪we␈α∩show␈α∪that␈α∩any␈α∪algorithm␈α∩in␈α∪the␈α∩␈↓↓quadratic
␈↓ α∧␈↓↓decision-tree model␈↓ must make ␈↓↓cn log n␈↓ tests for some input.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-734
␈↓"β␈↓ α∧␈↓    FAST ALGORITHMS FOR SOLVING PATH PROBLEMS
␈↓"β␈↓ α∧␈↓Author: Robert Endre Tarjan
␈↓"β␈↓ α∧␈↓49 pages␈↓ 
\Cost: $3.10

␈↓"β␈↓ α∧␈↓    Let␈α
G␈α
=␈α
(V,E)␈α
be␈α
a␈α
directed␈α
graph␈α
with␈α
a␈α
distinguished␈α
source␈α
vertex␈α
␈↓↓s␈↓.␈α
 The␈α
␈↓↓single-source
␈↓ α∧␈↓↓path␈α∩expression␈α∩problem␈↓␈α∩is␈α∩to␈α∩find,␈α∩for␈α∩each␈α∩vertex␈α∩␈↓↓v␈↓,␈α∩a␈α∩regular␈α∩epression␈α∩P␈↓↓(s,v)␈↓␈α⊃which
␈↓ α∧␈↓represents␈αthe␈αset␈αof␈αall␈αpaths␈αin␈αG␈αfrom␈α␈↓↓s␈↓␈αto␈α␈↓↓v␈↓.␈α A␈αsolution␈αto␈αthis␈αproblem␈αcan␈αbe␈αused␈αto
␈↓ α∧␈↓solve␈α⊂shortest␈α⊃path␈α⊂problems,␈α⊃solve␈α⊂sparse␈α⊂systems␈α⊃of␈α⊂linear␈α⊃equations,␈α⊂and␈α⊃carry␈α⊂out
␈↓ α∧␈↓global␈αflow␈αanalysis␈α[30].␈α We␈αdescribe␈αa␈αmethod␈αto␈αcompute␈αpath␈αexpressions␈αby␈αdividing
␈↓ α∧␈↓G␈α
into␈α
components,␈α
computing␈α
path␈α
expressions␈α
on␈α
the␈α
components␈α
by␈αGaussian␈α
elimination,
␈↓ α∧␈↓and␈α⊂combining␈α⊂the␈α∂solutions.␈α⊂ This␈α⊂method␈α∂requires␈α⊂O␈↓↓(m α(m,n))␈↓␈α⊂time␈α∂on␈α⊂a␈α⊂reducible␈α∂flow
␈↓ α∧␈↓graph,␈α
where␈α
␈↓↓n␈↓␈αis␈α
the␈α
number␈α
of␈αvertices␈α
in␈α
G,␈α␈↓↓m␈↓␈α
is␈α
the␈α
number␈αof␈α
edges␈α
in␈αG,␈α
and␈α
␈↓↓α␈↓␈α
is␈αa
␈↓ α∧␈↓functional␈α⊂inverse␈α⊃of␈α⊂Ackermann's␈α⊂function.␈α⊃ The␈α⊂method␈α⊂makes␈α⊃use␈α⊂of␈α⊂an␈α⊃algorithm␈α⊂for
␈↓ α∧␈↓evaluating␈α
functions␈α
defined␈α
on␈αpaths␈α
in␈α
trees␈α
[9,29].␈α A␈α
simplified␈α
version␈α
of␈αthe␈α
algorithm,
␈↓ α∧␈↓which␈α⊂runs␈α⊂in␈α⊂O␈↓↓(m␈α∂log␈α⊂n)␈↓␈α⊂time␈α⊂on␈α∂reducible␈α⊂flow␈α⊂graphs,␈α⊂is␈α∂quite␈α⊂easy␈α⊂to␈α⊂implement␈α∂and
␈↓ α∧␈↓efficient in practice.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-735
␈↓"β␈↓ α∧␈↓    KRONECKER'S CANONICAL FORM AND THE QZ ALGORITHM
␈↓"β␈↓ α∧␈↓Author:  J. H. Wilkinson
␈↓"β␈↓ α∧␈↓23 pages␈↓ 	¬Available in microfiche only.

␈↓"β␈↓ α∧␈↓    In␈α
the␈α
QZ␈α
algorithm␈α
the␈α
eigenvalues␈α
of␈α
A␈↓↓x␈α
=␈α
␈↓∧l␈↓B␈↓↓x␈↓␈α
are␈α
computed␈α
via␈α
a␈α
reduction␈α
to␈αthe␈α
form
␈↓ α∧␈↓␈↓¬~␈↓A␈↓↓x␈α
=␈α
␈↓∧l␈↓¬~␈↓B␈↓↓x␈↓␈αwhere␈α
␈↓¬␈↓A␈α
and␈α
␈↓¬␈↓B␈αare␈α
upper␈α
triangular.␈α
 The␈αeigenvalues␈α
are␈α
given␈α
by␈α␈↓∧l␈↓↓␈↓#vi␈↓#␈α
=␈α
a␈↓#vii␈↓#/b␈↓#vii␈↓#␈↓.␈α It␈α
is
␈↓ α∧␈↓shown␈αthat␈αwhen␈αthe␈αpencil␈α␈↓¬~␈↓A␈α-␈α␈↓∧l␈↓¬~␈↓B␈αis␈αsingular␈αor␈αnearly␈αsingular␈αa␈αvalue␈αof␈α␈↓∧l␈↓↓i␈↓␈αmay␈αhave␈αno
␈↓ α∧␈↓significance even when ␈↓¬~␈↓↓a␈↓#vii␈↓#␈↓ and ␈↓¬~␈↓↓b␈↓#vii␈↓#␈↓ are of full size.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-736
␈↓"β␈↓ α∧␈↓    NOTE ON THE PRACTICAL SIGNIFICANCE OF THE DRAZIN INVERSE
␈↓"β␈↓ α∧␈↓Author:  J. H. Wilkinson
␈↓"β␈↓ α∧␈↓20 pages␈↓ 	¬Available in microfiche only.

␈↓"β␈↓ α∧␈↓    The␈α
solution␈αof␈α
the␈α
differential␈αsystem␈α
B␈↓↓x␈α
=␈α␈↓A␈↓↓x␈α
+␈α
f␈↓␈αwhere␈α
A␈α
and␈αB␈α
are␈α
␈↓↓n␈α␈↓αx␈α
␈↓↓n␈↓␈αmatrices␈α
and
␈↓ α∧␈↓A␈α
-␈α
␈↓∧l␈↓B␈α
is␈α
not␈α
a␈αsingular␈α
pencil␈α
may␈α
be␈α
expressed␈α
in␈αterms␈α
of␈α
the␈α
Drazin␈α
inverse.␈α
 It␈αis␈α
shown
␈↓ α∧␈↓that␈α∩there␈α⊃is␈α∩a␈α∩simple␈α⊃reduced␈α∩form␈α∩for␈α⊃the␈α∩pencil␈α∩A␈α⊃-␈α∩␈↓∧l␈↓B␈α∩which␈α⊃is␈α∩adequate␈α∩for␈α⊃the
␈↓ α∧␈↓determination␈α∀of␈α∀the␈α∀general␈α∀solution␈α∃and␈α∀that␈α∀although␈α∀the␈α∀Drazin␈α∀inverse␈α∃could␈α∀be
␈↓ α∧␈↓determined efficiently from this reduced form it is inadvisable to do so.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-737
␈↓"β␈↓ α∧␈↓    ON THE AVERAGE-CASE COMPLEXITY OF SELECTING THE ␈↓↓k␈↓-th BEST
␈↓"β␈↓ α∧␈↓Author:  Andrew C. Yao & F. Frances Yao
␈↓"β␈↓ α∧␈↓45 pages␈↓ 
\Cost: $3.00

␈↓"β␈↓ α∧␈↓    Let␈α␈↓¬¬␈↓V␈↓↓␈↓#v(␈↓#n)␈↓␈αbe␈αthe␈αminimum␈αaverage␈αnumber␈αof␈αpairwise␈αcomparisons␈αneeded␈αto␈αfind␈αthe␈α␈↓↓k␈↓-
␈↓ α∧␈↓th␈α⊂largest␈α⊂of␈α⊃␈↓↓n␈↓␈α⊂numbers␈α⊂␈↓↓(k␈α⊂≥␈α⊃2)␈↓,␈α⊂assuming␈α⊂that␈α⊂all␈α⊃␈↓↓n!␈↓␈α⊂orderings␈α⊂are␈α⊂equally␈α⊃likely.␈α⊂ D.W.
␈↓ α∧␈↓Matula␈αproved␈α
that,␈αfor␈α
some␈αabsolute␈αconstant␈α
␈↓↓c␈↓,␈α␈↓¬¬␈↓V␈↓↓␈↓#vk␈↓#(n)-n␈α
≥␈αc␈αk␈α
log␈αlog␈α
n␈↓␈αas␈α␈↓↓n␈α
→␈α∞␈↓.␈α
 In␈αthe
␈↓ α∧␈↓present␈αpaper,␈αwe␈αshow␈αthat␈αthere␈αexists␈αan␈αabsolute␈αconstant␈α␈↓↓c'␈α>␈α0␈↓␈αsuch␈αthat␈α␈↓¬¬␈↓V␈↓↓␈↓#vk␈↓#(n)-n␈α≥
␈↓ α∧␈↓↓c' k log log n␈↓ as ␈↓↓n → ∞␈↓, proving a conjecture of Matula.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-738
␈↓"β␈↓ α∧␈↓    COMPUTATIONS RELATED TO G-STABILITY OF LINEAR MULTISTEP METHODS
␈↓"β␈↓ α∧␈↓Authors:  Randall LeVeque, Germund Dahlquist & Dan Andree
␈↓"β␈↓ α∧␈↓27 pages␈↓ 	¬Available in microfiche only.

␈↓"β␈↓ α∧␈↓    In␈α∪Dahlquist's␈α∩recent␈α∪proof␈α∩of␈α∪the␈α∩equivalence␈α∪of␈α∩A-stability␈α∪and␈α∪G-stability[1],␈α∩an
␈↓ α∧␈↓algorithm␈α∃was␈α⊗presented␈α∃for␈α∃calculating␈α⊗a␈α∃G-stability␈α∃matrix␈α⊗for␈α∃any␈α⊗A-stable␈α∃linear
␈↓ α∧␈↓multistep␈αmethod.␈α Such␈αmatrices,␈αand␈αvarious␈αquantities␈αcomputable␈αfrom␈αthem,␈αare␈αuseful
␈↓ α∧␈↓in␈αmany␈αaspects␈αof␈αthe␈αstudy␈αof␈αthe␈αstability␈αof␈αa␈αgiven␈αmethod.␈α For␈αexample,␈αinformation
␈↓ α∧␈↓may␈α∞be␈α∂gained␈α∞as␈α∂to␈α∞the␈α∞shap␈α∂of␈α∞the␈α∂stability␈α∞region,␈α∞or␈α∂the␈α∞rate␈α∂of␈α∞growth␈α∂of␈α∞unstable
␈↓ α∧␈↓solutions.␈α We␈αpresent␈αa␈αsummary␈αof␈αthe␈αrelvant␈αtheory␈αand␈αthe␈αresults␈αof␈αsome␈αnumerical
␈↓ α∧␈↓calculations␈αperformed␈αfor␈αseveral␈αbackward␈αdifferentiation,␈αAdams-Bashforth,␈αand␈αAdams-
␈↓ α∧␈↓Moulton methods of low order.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓HPP-79-14
␈↓"β␈↓ α∧␈↓    INDUCTION OVER LARGE DATA BASES
␈↓"β␈↓ α∧␈↓Author:  J. R. Quinlan
␈↓"β␈↓ α∧␈↓19 pages␈↓ 
\Cost: $2.25

␈↓"β␈↓ α∧␈↓    Techniques␈α∂for␈α⊂discovering␈α∂rules␈α⊂by␈α∂induction␈α⊂from␈α∂large␈α⊂collections␈α∂of␈α⊂instances␈α∂are
␈↓ α∧␈↓developed.␈α∞ These␈α∞are␈α∞based␈α∞on␈α∞an␈α∂iterative␈α∞scheme␈α∞for␈α∞dividing␈α∞the␈α∞instances␈α∂into␈α∞two
␈↓ α∧␈↓sets,␈αonly␈αone␈αof␈αwhich␈αneeds␈αto␈αbe␈αrandomly␈αaccessible.␈α These␈αtechniques␈αhave␈αmade␈αit
␈↓ α∧␈↓possible␈α⊗to␈α↔discover␈α⊗complex␈α↔rules␈α⊗from␈α↔data␈α⊗bases␈α↔containing␈α⊗many␈α↔thousands␈α⊗of
␈↓ α∧␈↓instances.  Results of several experiments using them are reported.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-740
␈↓"β␈↓ α∧␈↓    THE LOGIC OF ALIASING
␈↓"β␈↓ α∧␈↓Authors:  R. S. Cartwright and D. C. Oppen
␈↓"β␈↓ α∧␈↓?  pages␈↓ ≥Cost: $

␈↓"β␈↓ α∧␈↓    We␈α
give␈α
a␈α
new␈α
version␈α
of␈α
Hoare's␈α
logic␈α
which␈α
correctly␈α
handles␈α
programs␈α
with␈α
aliased
␈↓ α∧␈↓variables.␈α  The␈α
central␈αproof␈α
rules␈αof␈α
the␈αlogic␈α
(procedure␈αcall␈α
and␈αassignment)␈αare␈α
proved
␈↓ α∧␈↓sound and complete.
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-

␈↓"β␈↓ α∧␈↓Author:
␈↓"β␈↓ α∧␈↓   pages␈↓ ≥Cost: $
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-

␈↓"β␈↓ α∧␈↓Author:
␈↓"β␈↓ α∧␈↓   pages␈↓ ≥Cost: $
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-
␈↓ α∧␈↓Author:
␈↓"β␈↓ α∧␈↓   pages␈↓ ≥Cost: $
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-

␈↓"β␈↓ α∧␈↓Author:
␈↓"β␈↓ α∧␈↓   pages␈↓ ≥Cost: $
␈↓"β␈↓ α∧␈↓-␈↓ v-
␈↓"β␈↓ α∧␈↓STAN-CS-79-

␈↓"β␈↓ α∧␈↓Author:
␈↓"β␈↓ α∧␈↓   pages␈↓ ≥Cost: $
␈↓"β␈↓ α∧␈↓-␈↓ v-